TOC-Turing Machine

• Turing Machines are general purpose, meaning that they can take the encoding of a computation model and simulate the behavior.
• Turing Machines are more powerful than modern computers. Whatever we can do on a computer, Turing Machines can do the same.
• Turing Machines have the same computational power as $\lambda$ - calculus. (By Alonzo Church) and recursion functions (by Kurt Godel).
• Even Turing Machines are not ultimate. Those unsolvable problems are beyond the limit of computation.

Definition

A Turing Machine is a 7-tuple:

$$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_{accept},q_{reject}),$$

where $Q,\mathrm{\Sigma },\mathrm{\Gamma }$ are finite sets, and:

1. $Q$ is the set of states,
2. $\mathrm{\Sigma }$ is the input alphabet ($\bigsqcup \notin \mathrm{\Sigma }$),
3. $\mathrm{\Gamma }$ is the tape alphabet ($\bigsqcup \in \mathrm{\Gamma }$ and $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$),
4. $\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$ is the transition function,
5. $q_0\in Q$ is the start state,
6. $q_{accept}\in Q$ is the accept state, and
7. $q_{reject}\in Q$ is the reject state, where $q_{reject}\ne q_{accept}$.

A Turing Machine can be described as

• a control unit, which a state machine;
• an infinite tap;
• the control unit can read and write on the tap;
• the control unit can move left and right;
• the control unit has special states for rejecting and accepting take immediate effect.

Example

Let $B=\{s\mathrm{\#}s\mid s\in \{0,1{\}}^{\ast }\}$ and a Turing Machine $M$ be described as follows to recognize $B$. $M$ operates on input string $w$ as follows:

1. Read the input $w$ onto the tape.

2. Ensure that $w$ has exactly one $\mathrm{\#}$, otherwise reject.

3. Zig-zag across the tape to the corresponding positions on either side of $\mathrm{\#}$ to check whether these positions contain the same symbol.

   • Cross out the symbols if they are the same; otherwise, reject.

4. When all symbols to the left of $\mathrm{\#}$ are crossed out, check the symbols to the right of $\mathrm{\#}$.

   • If all are crossed out, accept; otherwise, reject.

---

$B=\{s\mathrm{\#}s|s\in \{0,1{\}}^{\ast }\}$ is not context free.

Problem: Input: Given a string $\alpha$ in $\{0,1,\mathrm{\#}{\}}^{\ast }$ Question: Is $\alpha \in B$?

Algorithm:

1. load $\alpha$ on to memory
2. Check if $\alpha$ has only one #, reject if no
3. Repeat until no unmarked symbol
   • Find the first unmarked symbol in first half
   • Go right, exceed find the first unmarked symbol in second half
   • mark s'
   • reject if $s\ne s^{\prime }$
   • go left exceed find the first unmarked symbol in first half
4. accept if no more in second half.

+ Formal Definition

The above example shows the basic features of a Turing Machine.

• (Preprocessing) Read the input (over an alphabet $\mathrm{\Sigma }$) onto the tape and move the head to the first symbol in the input.

• Note: The preprocessing is trivial, tedious, and required by every Turing Machine (TM). Thus, this part of the TM is always omitted.

• To cross out symbols, a set of tape symbols $\mathrm{\Gamma }$ has to be defined.

  • $\mathrm{\Gamma }$ also contains a blank symbol $\bigsqcup$ to show that a tape cell is empty.
  • $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$.

• $q_0\in Q$ is the start state.

• $q_{accept}\in Q$ is the accept state.

• $q_{reject}\in Q$ is the reject state, where $q_{reject}\ne q_{accept}$.

• The state machine has a transition function:

  $$\delta :Q\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$$

  of the input:

  • A current state in $Q$, and
  • A tape symbol in $\mathrm{\Gamma }$ in the cell currently pointed to by the state machine.

• And of the output:

  • The next state in $Q$,
  • The new tape symbol in $\mathrm{\Gamma }$ replacing the symbol in the current cell, and
  • Either $L$ or $R$, the direction that the state machine is moving.

Computation on TMs

Accept A TM $M$ accepts a string $w$ if it halts on the input $w$ at an accepting state.

Reject A TM $M$ rejects a string $w$ if it halts on the input $w$ at a reject state.

If the transition function is only a partial function (some elements in the domain is undefined),

A TM $M$ rejects a string $w$ if

• it halts on the input $w$ at a reject state, or
• it has no where to move in the middle of the process.

Using a partial transition function can omit the reject states. To make a partial function be total, we just artificially add those undefined transitions to a reject state.

Language

The language for TM are of two types.

A language $L$ is recursive or Turing-decidable if there is a TM $M$ such that

• $\mathrm{\forall }w\in L$, $M$ accepts $w$; and
• $\mathrm{\forall }w\notin L$, $M$ rejects $w$.

We say $M$ decides $L$.

A language $L$ is recursively enumerable (or Turing-recognizable) if there is a TM $M$ such that

• $\mathrm{\forall }w\in L$,$M$ accepts $w$; and
• $\mathrm{\forall }w\notin L$, $M$ rejects $w$ or $M$ loops forever.

We say $M$ recognizes $L$.

Side Effect

When a TM halts on an input,

• the current state "accept" or "reject" is the output;
• the content remains on its tape is the side effect.

A TM has a side effect if users need to read tape content to get the desired output. (Using only states of the TM is insufficient to express the output.)

If a TM has no side effect and is only used for checking its output, it is pure; otherwise, it is impure.